#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 插入排序（带哨兵，从小到大排序，升序）
// HINT: 原始序列中，第一个位置作为哨兵，与真实数据序列无关。所以，我们最终排序结果应该从第二个元素开始算起，一直到最后一个元素。其中，我们认为第一个有效元素是自然有序的。则应从索引为3的元素开始拿，往前面插入。
// REVIEW: 我们的解决办法是：把当前轮次需要插入的数据保存在数组的第一个元素处。（后简称”哨兵“）我们可以用两层循环来实现。外层循环每做完一轮，无序段的第一个元素就成功插入有序段中。内层循环负责当前轮次下的数据乾坤大挪移。将哨兵和有序段末最大的元素开始比较起，如果哨兵比有序段的元素小，执行将比他大的数往后挪一位，再比较倒数第2个数是否比哨兵大。如果是往后挪……如此往复，直到找不到任何有序段元素比哨兵还小，此时就找到了待查元素的位置。将哨兵保存到该位置，外层循环的一轮即完成。【注】我们不必担心有序段在变长时，会覆盖掉原待插数。因为已经实现把数据保存到了哨兵位置，所以不影响。
void InsertSort(ElemType A[], int n) {
	// NOTE: 定义临时变量（用于表示索引）
	// REVIEW: i和j都是索引。i存放的是待插元素的索引；j用于控制内层循环在乾坤大挪移时，元素的索引。
	int i, j;


	// NOTE: 进行插入排序
	for (i = 2; i <= n; ++i) {
		if (A[i] < A[i - 1]) {
			// STEP: 将索引为i的元素放置到哨兵处，即A[0]
			A[0] = A[i];

			// STEP: “乾坤大挪移”。将待插元素从有序段的尾部开始，逐个元素比较大小。并视情况，移动有序段末尾的元素。
			for (j = i - 1; A[0] < A[j]; --j) {
				A[j + 1] = A[j];
			}

			// STEP: 把哨兵插入到对应位置
			A[j + 1] = A[0];
		}
	}
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	// HINT: 实际申请了11个元素空间
	ST_Init(ST, 10);
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 插入排序
	InsertSort(ST.elem, 10);


	return 0;
}